The present invention relates generally to field of network addressing. More specifically, the present invention is directed to a method and an apparatus for managing a ternary content addressable memory (TCAM) table.
Internet Protocol (IP) is a source route type of network where forwarding is made based on a destination Internet address. Address forwarding is made on a hop-by-hop basis. The destination address is looked up in a routing table to determine where a next hop is. The packet is then forwarded to the next hop. A routing protocol is used to make sure that as the packet travels through the network it will eventually reaches its destination.
The growth of the Internet causes routing tables to grow faster than the router technology. The router would have to keep millions of entries in its database corresponding to the millions of computers on the Internet. The look up process of the destination address in the routing table is an important part of the IP forwarding process. One of the Internet protocols is IP version 4 (xe2x80x9cIPv4xe2x80x9d). The address space for the IPv4 is 32 bits wide. Under the IPv4, there are two schemes of IP addresses. One IP address scheme is xe2x80x9cclassfulxe2x80x9d, while another IP address scheme is xe2x80x9cclasslessxe2x80x9d. Each IP or Internet address comprises a network id and a host id. The network id identifies the network on which the host resides. The network id is sometimes referred to as a network prefix. The host id identifies the particular host on the given network. The classful IP address scheme comprises multiple classes: A, B, C, D and E. Under class A, the network id is 8 bits wide, and the host id is 24 bits wide. Under class B, the network id is 16 bits wide, and under class C the network id is 24 bits wide. Each of the classes is used to support different size networks having different number of hosts. Network ids of all zeroes and all ones are reserved for default route and loop back function respectively. Class D is used for multicast, and class E is reserved. The classful IP address scheme does not efficiently accommodate different sizes of networks. Routers in the xe2x80x9cold stylexe2x80x9d networks generally use the classful IP address scheme.
The classless IP address scheme is often referred to as CIDR (xe2x80x9cclassless inter-domain routingxe2x80x9d). Basically, CIDR eliminates the concept of class A, B, and C networks and replaces this with an IP address prefix. CIDR can be used to perform route aggregation in which a single route can cover the address space of several xe2x80x9cold-stylexe2x80x9d network numbers and thus replaces a lot of the old routes. CIDR makes it possible to utilize the available address space more efficiently and allows for continuous, uninterrupted growth of the Internet. Newer routers use the CIDR address scheme.
IP packet forwarding is processed at each router. To accelerate the lookup process, a set of address prefixes is stored as compared to millions of Internet addresses. Route lookup using the address prefixes is referred to as longest prefix match. In longest prefix match, each destination address is a string of 32 bits. The forwarding decision relies on using the destination address and finding an entry having the longest prefix match. The destination address is compared against the set of address prefixes to find a next route to forward the packet. There may be multiple prefix matches, however, the route having the longest prefix match would be selected. The longest match algorithm assumes that the host is part of the network having the longest prefix match.
The traditional lookup process is software based using hashes and trees. There may be multiple lookup per packet. However, as the number of packets increases, faster look up processes are necessary. One hardware lookup approach uses high-speed ternary content-addressable memory (TCAM). TCAM is a memory device that provides fast searches such as looking up for an entry in a route table database. TCAM allows retrieval of a location of a content given a partial content. Thus given a content (e.g., destination address), TCAM provides a location information (e.g., route) to that content. In addition, TCAM allows masking on bit fields and as such can be used to determine longest prefix matches. Each TCAM memory location has a corresponding mask register. A xe2x80x9c1xe2x80x9d in the mask register forces a match on the corresponding bit in the TCAM memory location where an address of a next hop for a next route is pre-stored. The prefix is stored in the mask register.
Management of the TCAM memory (xe2x80x9cTCAM tablexe2x80x9d) is essential to provide the correct longest prefix match in the shortest time.
A method and a system for managing a TCAM table are disclosed. A new route is inserted into the TCAM table at an available location using an index. The new route is added into a Patricia tree organized by a mask length associated with the new route. Routes having common prefixes with the new route are searched for in Patricia trees organized by longer mask lengths and in Patricia trees organized by shorter mask lengths to locate a chain for the new route. The chain for the new route groups routes having common prefixes. The routes in the chain are sequenced in an order of longer prefix first such that a route at a top of the chain has a longest prefix. A swap of routes in the chain is performed to accommodate the new route and to maintain the longer prefix first order.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.